#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DataType;
typedef struct Stack
{
	DataType* data;
	int top;
	int capacity;
}Stack;

void Init(Stack* st);
void Push(Stack* st, DataType x);
void Pop(Stack* st);
DataType GetTop(Stack* st);
bool Empty(Stack* st);
void Destroy(Stack* st);
int Size(Stack* st);

void Init(Stack* st)
{
	assert(st);

	st->data = NULL;
	st->top = 0;
	st->capacity = 0;
}

void Push(Stack* st, DataType x)
{
	assert(st);

	if (st->capacity == st->top)
	{
		int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2;

		DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		st->data = temp;
		st->capacity = newcapacity;
	}

	st->data[st->top++] = x;
}

void Pop(Stack* st)
{
	assert(st);
	assert(st->top > 0);

	st->top--;
}

DataType GetTop(Stack* st)
{
	assert(st);
	assert(st->top > 0);

	return st->data[st->top - 1];
}

bool Empty(Stack* st)
{
	assert(st);

	return (st->top == 0);
}

void Destroy(Stack* st)
{
	assert(st);

	free(st->data);
	st->data = NULL;
	st->top = st->capacity = 0;

}

int Size(Stack* st)
{
	assert(st);

	return st->top;
}

typedef struct
{
	Stack push;
	Stack pop;
} MyQueue;


MyQueue* myQueueCreate()
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	Init(&obj->push);
	Init(&obj->pop);

	return obj;
}

void myQueuePush(MyQueue* obj, int x)
{
	Push(&obj->push, x);
}

int myQueuePop(MyQueue* obj)
{
	int ret = myQueuePeek(obj);
	Pop(&obj->pop);

	return ret;
}

int myQueuePeek(MyQueue* obj)
{
	if (Empty(&obj->pop))
	{
		int size = Size(&obj->push);
		for (int i = 0; i < size; i++)
		{
			Push(&obj->pop, GetTop(&obj->push));
			Pop(&obj->push);
		}
	}

	return GetTop(&obj->pop);
}

bool myQueueEmpty(MyQueue* obj)
{
	return Empty(&obj->pop) && Empty(&obj->push);
}

void myQueueFree(MyQueue* obj)
{
	free((&obj->push)->data);
	free((&obj->pop)->data);
	free(obj);
}
